/**
 * 二分匹配算法
 */
export const bipartiteMatch = (left: string[], right: string[], matchSet: Set<string>) => {
    const result: Record<string, string> = {}
    const used = new Map<string, boolean>()
    const dfs = (u: string) => {
        for (const v of right) {
            if (!used.get(v) && matchSet.has(u + v)) {
                used.set(v, true)
                if (!result[v] || dfs(result[v])) {
                    result[v] = u
                    return true
                }
            }
        }
        return false
    }
    for (const u of left) {
        used.clear()
        dfs(u)
    }

    // 将 result 的 key 和 value 换位置后返回
    const newResult: Record<string, string> = {}
    for (const key in result) {
        newResult[result[key]] = key
    }
    return newResult
}

/**
 * 爬与位置的二分匹配
 */
export const creepPosBipartiteMatch = (creeps: Creep[], pos: RoomPosition[], range = 1) => {
    const matchSet = new Set<string>()
    const left = creeps.map((creep) => creep.name)
    const right = pos.map((p) => `${p.x}/${p.y}`)

    const getRange = (x1: number, y1: number, x2: number, y2: number) => Math.max(Math.abs(x1 - x2), Math.abs(y1 - y2))

    creeps.forEach((creep) => {
        pos.forEach((p) => {
            if (getRange(creep.pos.x, creep.pos.y, p.x, p.y) > range) return

            matchSet.add(`${creep.name}${p.x}/${p.y}`)
        })
    })

    const match = bipartiteMatch(left, right, matchSet)

    const posMap = new Map<string, RoomPosition>()
    pos.forEach((p) => posMap.set(`${p.x}/${p.y}`, p))

    const result: Record<string, RoomPosition> = {}
    for (const creepName in match) {
        const posKey = match[creepName]
        result[creepName] = posMap.get(posKey)!
    }

    return result
}
